import java.util.*;

public class ValidParentheses {
    /*
    * 有效的括号
    * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    * 有效字符串需满足：
    * 左括号必须用相同类型的右括号闭合。
    * 左括号必须以正确的顺序闭合。
    * 每个右括号都有一个对应的相同类型的左括号。
    *
    * 1 <= s.length <= 10(4)
    * s 仅由括号 '()[]{}' 组成
    * */
    public static void main(String[] args){
        ValidParentheses validParentheses = new ValidParentheses();
        validParentheses.mySolution("({{{{}}}))");
    }

    // 我的想法：遇到左符号就入栈，遇到非左符号就弹栈，
    // 两者对比匹配，利用两字符之间的差值判断是否匹配
    // tips: 入栈的时候直接入右括号，这样之后比较的时候就不用算值，直接看相不相等就完了
    public boolean mySolution(String s){
        if(s.length() % 2 != 0)
            return false;
        Deque<Character> checkDeque = new ArrayDeque<>(s.length()/2);
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // s入栈
            if(c == '(' || c == '{' || c == '[')
                checkDeque.add(s.charAt(i));
            // 开始匹配
            else{
                // 为空说明已经没左符号了，不匹配
                if(checkDeque.isEmpty())
                    return false;
                char last = checkDeque.pollLast();
                // 这里要小心负数！！！
                if (Math.abs(c - last) > 2)
                    return false;
            }
        }
        return checkDeque.isEmpty();
    }
}
